1. Field of the Invention
The present invention relates to a QR decomposition apparatus and method in a Multiple Input Multiple Output (MIMO) system; and, more particularly, to a QR decomposition apparatus and method that can reduce the number of computers by sharing hardware in an MIMO system employing Orthogonal Frequency Division Multiplexing (OFDM) technology to thereby simplify a structure of hardware.
This work was partly supported by the IT R & D program of MIC/IITA [2006-S-002-02, “IMT-Advanced Radio Transmission Technology with Low Mobility”].
2. Description of Related Art
At present, there are increasing demands for wireless communication system capable of transmitting high-quality and large-volume multimedia data by using limited frequency resources. Among the methods for transmitting large-volume data by using limited frequency resources is a Multiple Input Multiple Output (MIMO) system. An MIMO system forms a plurality of independent fading channels by using multiple antennas at transmitting and receiving ends and transmits different signals for each transmission antenna to thereby improve a data transmission rate remarkably. Thus, the MIMO system can transmit a great deal of data without broadening frequency.
However, MIMO systems are weak to inter-symbol interference and frequency selective fading that are caused during high-speed data transmission. To overcome the shortcoming, the MIMO systems employ Orthogonal Frequency Division Multiplexing (OFDM) technology. OFDM is a modulation scheme most appropriate for high-speed data transmission at present. According to OFDM, one data sequence is transmitted over subcarrier which is transmitted at a lower data transmission rate than that of the data sequence.
Typically, a channel environment for wireless communication has multiple paths, which is called multipath, due to obstacles such as buildings. Delay spread occurs in wireless channel having multipath due to the multipath. When delay spread time is longer than symbol transmission interval, inter-symbol interference (ISI) occurs. In this case, frequency selective fading occurs in a frequency domain. When a single carrier is used, an equalizer is used to remove the inter-symbol interference components. However, as data rate increases, the equalizer becomes more complicated.
When an MIMO system is combined with an OFDM system, the advantages of the MIMO system can be taken while the disadvantage of the MIMO system is offset by the OFDM system. Typically, an MIMO system has N transmission antennas and M reception antennas. A structure combining the MIMO system with the OFDM technology is referred to as a MIMO-OFDM system.
FIGS. 1A and 1B are block views showing structures of an MIMO-OFDM system. FIG. 1A is a block view illustrating a transmitting end of the MIMO-OFDM system, and FIG. 1B is a block view illustrating a receiving end of the MIMO-OFDM system.
Referring to FIG. 1A, a serial-to-parallel (S/P) converter 101 divides transmission data into a plurality of parallel data sequences. A plurality of encoders 102 encode a parallel data sequence, respectively. Each encoded data sequence is modulated in a Quadrature Amplitude Modulation (QAM) mapper 103 based on a modulation scheme, such as Binary Phase Shift Keying (BPSK), Quadrature Phase Shift Keying (QPSK), 16QAM, and 64QAM, respectively, to thereby produce modulated symbols. The modulated symbols are converted into signals of a time axis in an Inverse Fast Fourier Transformer (IFFT) 104. A cyclic prefix (CP) inserter 105 inserts a cyclic prefix code for guard interval to the time-axis symbols. Subsequently, a digital-to-analog conversion (DAC) and radio frequency (RF) unit 106 converts the digital signals with the CP code inserted thereto into analog signals, converts the analog signals into RF signals, and sends out the RF signals through an antenna.
Referring to FIG. 1B, a digital-to-analog conversion (ADC) and RF unit 107 converts the RF signals into analog signals and converts the analog signals into digital signals. A CP remover 108 removes the CP code inserted for guard interval and transmits signals without a CP code to a Fast Fourier Transformer (FFT) 109. The FFT 109 executes high-speed Fourier conversion onto the inputted parallel signals to thereby generate transmission data symbols. An MIMO receiver 110 estimates the generated transmission data symbols and calculates a log likelihood ratio (LLR) of the estimated symbols. Decoders decode the data sequences transmitted from the MIMO receiver 110, respectively, and estimates transmission data. A parallel-to-serial (P/S) converter 112 converts the decoded parallel data outputted from the decoders 111.
Examples of the MIMO receiver 110 include a Decision Feedback Equalizer (DFE), a zero forcing (ZF) device, a Minimum Mean Square Error Estimator (MMSE), and a Bell Labs Layered Space-Time (BLAST) device. As the MIMO receiver includes more transmission and reception antennas, the complexity of the MIMO receiver becomes high and, particularly, the complexity of QR decomposition increases greatly.
When it is assumed that there are M antennas and the number of reception antennas is N, a reception vector z of arbitrary subcarrier after FFT can be expressed as the following Equation 1.
                                              ⁢                              z            =                        ⁢                          Hs              +              n                                ⁢                                          ⁢                                          ⁢          where          ⁢                                          ⁢                                    z              =                              [                                                                                                    z                        1                                                                                                                                                z                        2                                                                                                                        ⋮                                                                                                                          z                        N                                                                                            ]                                      ;                    ⁢                                          ⁢                      channel            ⁢                                                  ⁢                          (              H              )                        ⁢                                                  ⁢            is                    ⁢                                          ⁢                                          ⁢                                    H              =                              [                                                                                                    h                                                  1                          ,                          1                                                                                                                                    h                                                  1                          ,                          2                                                                                                            …                                                                                      h                                                  1                          ,                          M                                                                                                                                                                        h                                                  2                          ,                          1                                                                                                                                    h                                                  2                          ,                          2                                                                                                            …                                                                                      h                                                  2                          ,                          M                                                                                                                                                ⋮                                                              ⋮                                                              ⋱                                                              ⋮                                                                                                                          h                                                  N                          ,                          1                                                                                                                                    h                                                  N                          ,                          2                                                                                                            …                                                                                      h                                                  N                          ,                          M                                                                                                                    ]                                      ;                    ⁢                                          ⁢                      and            ⁢                                                  ⁢            a            ⁢                                                  ⁢            transmission            ⁢                                                  ⁢            symbol            ⁢                                                  ⁢                          (              s              )                        ⁢                                                  ⁢            is                    ⁢                                          ⁢                                          ⁢                      s            =                                          [                                                                                                    s                        1                                                                                                                                                s                        2                                                                                                                        ⋮                                                                                                                          s                        M                                                                                            ]                            .                                                          Eq        .                                  ⁢        1            
The channel (H) may be expressed as H=QR after QR decomposition. Generally, the number N of reception antennas is equal to or greater than the number M of transmission antennas in an MIMO system, an upper triangular R matrix is expressed as Equation 2.
                              R          =                                                    Q                H                            ⁢              H                        =                          [                                                                                          r                                              1                        ,                        1                                                                                                                        r                                              1                        ,                        2                                                                                                  …                                                                              r                                              1                        ,                        M                                                                                                                                  0                                                                              r                                              2                        ,                        2                                                                                                  …                                                                              r                                              2                        ,                        M                                                                                                                                  ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                        0                                                        0                                                        …                                                                              r                                              M                        ,                        M                                                                                                                                  0                                                        0                                                        …                                                        0                                                                                        ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                        0                                                        0                                                        …                                                                              0                                              N                        ,                        M                                                                                                        ]                                      ⁢                                  ⁢                  where          ⁢                                          ⁢          Q          ⁢                                          ⁢          denotes          ⁢                                          ⁢          a          ⁢                                          ⁢          unitary          ⁢                                          ⁢          matrix          ⁢                                          ⁢                      (                                                            Q                  H                                ⁢                Q                            =              I                        )                                              Eq        .                                  ⁢        2            
The channel matrix (H) is N×M; Q=N×N; and the upper triangular R matrix is N×M. Herein, the Q can be expressed as:
  Q  =            [                                                  q                              1                ,                1                                                                        q                              1                ,                2                                                                        q                              1                ,                3                                                                        q                              1                ,                4                                                          …                                              q                              1                ,                N                                                                                        q                              2                ,                1                                                                        q                              2                ,                2                                                                        q                              2                ,                3                                                                        q                              2                ,                4                                                          …                                              q                              2                ,                N                                                                                        q                              3                ,                1                                                                        q                              3                ,                2                                                                        q                              3                ,                3                                                                        q                              3                ,                4                                                          …                                              q                              3                ,                N                                                                                        q                              4                ,                1                                                                        q                              4                ,                2                                                                        q                              4                ,                3                                                                        q                              4                ,                4                                                          …                                              q                              4                ,                N                                                                          ⋮                                ⋮                                ⋮                                ⋮                                ⋱                                ⋮                                                              q                              N                ,                1                                                                        q                              N                ,                2                                                                        q                              N                ,                3                                                                        q                              N                ,                4                                                          ⋯                                              q                              N                ,                N                                                        ]        .  
Accordingly, the modified reception vector y is expressed as the following Equation 3.
                                                        y              =                            ⁢                                                [                                                                                                              y                          1                                                                                                                                                              y                          2                                                                                                                                    ⋮                                                                                                                                      y                          N                                                                                                      ]                                =                                                                            Q                      H                                        ⁢                    z                                    =                                      Rs                    +                                          n                      ′                                                                                                                                              =                            ⁢                                                                    [                                                                                                                        r                                                          1                              ,                              1                                                                                                                                                            r                                                          1                              ,                              2                                                                                                                                …                                                                                                      r                                                          1                              ,                              M                                                                                                                                                                            0                                                                                                      r                            22                                                                                                    …                                                                                                      r                                                          2                              ,                              M                                                                                                                                                                            0                                                                          ⋮                                                                          ⋱                                                                          ⋮                                                                                                                      0                                                                          …                                                                          0                                                                                                      r                                                          N                              ,                              M                                                                                                                                            ]                                    ⁡                                      [                                                                                                                        s                            1                                                                                                                                                                            s                            2                                                                                                                                                ⋮                                                                                                                                                  s                            M                                                                                                                ]                                                  +                                                      [                                                                                                                        n                            1                            ′                                                                                                                                                                            n                            2                            ′                                                                                                                                                ⋮                                                                                                                                                  n                            N                            ′                                                                                                                ]                                    .                                                                                        Eq        .                                  ⁢        3            
The Equation 3 can be simply expressed as follows.
                    y        =                ⁢                              [                                                                                y                    1                                                                                                                    y                    2                                                                                                ⋮                                                                                                  y                    M                                                                        ]                    =                                                    Q                H                            ⁢              z                        =                          Rs              +                              n                ′                                                                            =                ⁢                                            [                                                                                          r                                              1                        ,                        1                                                                                                                        r                                              1                        ,                        2                                                                                                  …                                                                              r                                              1                        ,                        M                                                                                                                                  0                                                                              r                      22                                                                            …                                                                              r                                              2                        ,                        M                                                                                                                                  0                                                        ⋮                                                        ⋱                                                        ⋮                                                                                        0                                                        …                                                        0                                                                              r                                              M                        ,                        M                                                                                                        ]                        ⁡                          [                                                                                          s                      1                                                                                                                                  s                      2                                                                                                            ⋮                                                                                                              s                      M                                                                                  ]                                +                                    [                                                                                          n                      1                      ′                                                                                                                                  n                      2                      ′                                                                                                            ⋮                                                                                                              n                      M                      ′                                                                                  ]                        .                              
Gram-Schmidt method is known as a simple method among other methods for QR decomposition. The following Equation 4 describes a typical QR decomposition method. Referring to the Equation 4, a norm, which is a vector size, is calculated first (norm1=∥qi∥2), and a Q column value for a reception vector is calculated (qi:=qi/ri,j) by obtaining ri,j for √{square root over (normi)}. Subsequently, an R column value is calculated based on the obtained Q column value and the reception vector, and a Q update value and a norm update value are calculated. This process is repeated until nT is decided by the transmission and reception antennas.
R = 0,Q = Hfor i = 1,...,nT normi =|| qi ||2endfor i = 1,...,nT ri,i = {square root over (normi)} qi := qi / ri,i for k = i + 1,...,nT  ri,k = qiH ·qk  qk := qk −ri,k ·qi  normk := normk −ri,k2 endendEq. 4
To take an example where nT=8 in the Equation 4, more than 2000 multipliers and 8 dividers are required. Also, it takes 256 multipliers for QHz real part computation. In total, the number of entire multipliers comes to more than 2200, which are too many to be realized as hardware.